A communication channel linking a first transceiver to a second transceiver carries signals between the two. Regardless of which device transmits and which device receives, the channel typically corrupts a transmitted signal by altering the latter's amplitude and phase characteristics at frequencies across the channel's spectrum. As a result, the receiver receives a noisy version of the transmitted signal. If the nature of the corruption varies with time, the channel is considered to be a time-varying channel. If, on the other hand, the nature of the corruption does not change with time, or changes very slowly relative to the duration of a transmission, the channel is considered to be a time-invariant channel. For time-invariant channels, the corruption experienced by a transmitted signal can be predicted by estimating the channel's impulse response (CIR), which is a representation of the extent of spreading experienced by an impulse transmitted over that channel. One may estimate a time-invariant channel's CIR by transmitting a plurality of known training signals at known times, receiving the channel-corrupted training signals, and then calculating the CIR by techniques such as Least Mean Squares (LMS), among others. Once the CIR of a channel has been calculated, one may develop a channel equalizer to compensate for the corruption experienced by a transmitted signal.
FIG. 1 presents a block diagram of a typical Digital Subscriber Line (xDSL) modem, for HDSL, ADSL, SDSL, VDSL and similar communication. xDSL modems represent the next generation of high-speed digital communications for the Small-Office/Home-Office (SOHO) environment, as well as the burgeoning home user market which has been spurred on by the Internet. As seen in the diagram of FIG. 1, a typical xDSL modem 100 comprises a communication controller 102 to interface with a local network, computer or other equipment, a transceiver 04 and a line driver 106 which interfaces with a twisted-pair transmission line. It should be understood that xDSL modems may have other components and connections as well, and that the blocks shown may not always be present in a single unit.
FIG. 2a shows a block diagram of the modem's transceiver 104. The transceiver 104 includes an analog front end 114, a signal processor 112 and a digital interface 110. The analog front end 114 typically includes a D.C. isolating transformer, filters and amplifiers to connect to the line driver 106, and ADCs and DACs to interface the signal to and from the line driver to the signal processor 112. The digital interface 110 includes circuitry to interface the processed signal output from the signal processor 112 to the communication controller 102.
The signal processor 112 handles a number of functions. These functions may include such things as modulating and demodulating signals, echo cancellation, clipping mitigation, and filtering, among others. Thus, the signal processor 112 is used to convert the transmitted and received digital signals from one form to another. The signal processor 112 is typically implemented through a combination of hardware and executable software code. In the usual case, the signal processor includes a programmable computer, perhaps implemented as a reduced instruction set (RISC) computer, which handles only a handful of specific tasks. The computer is typically provided with at least one computer readable medium, such as a PROM, flash, or other non-volatile memory to store firmware and executable software code, and will usually also have an associated RAM or other volatile memory to provide workspace for data and additional software.
In the typical xDSL communication system, the signals handled by the signal processor 112 are discrete multitone signals (DMTs) comprising N/2 discrete tones simultaneously carried over the twisted pair. The collection of discrete tones is commonly referred to as a symbol, and a sequence of such symbols, spaced apart in time by a sacrificial prefix, are transmitted in xDSL communications. However, signal corruption by the twisted-pair may cause samples comprising one symbol to overlap with samples comprising adjacent symbols despite the presence of the sacrificial prefix. This phenomenon is called inter-symbol interference (ISI). In addition to ISI, another effect of channel corruption is that different DMT tones are attenuated and delayed to different degrees by the twisted pair channel and so may be unwieldy to process later on.
FIG. 2b illustrates some of the functions served by the signal processor 112 when receiving an xDSL signal during normal operation. Once the incoming DMT signal has been sampled by an analog-to-digital converter, the sampled signal is passed through a time domain filter 112a (TDF) to help mitigate ISI. The filtered sampled signal is then buffered in a serial-to-parallel converter 112b where the prefix is stripped and the DMT symbol is formatted and subjected to an N-length DFT, normally implemented as an FFT 112c, to convert the signal into N/2 complex discrete frequency coefficients. The complex signal is then subjected to a frequency domain equalizer 112d (FEQ) which accounts for the uneven attenuation and phase delay of the DMT symbol across the various frequencies. After passing through the FEQ 112d, the individual frequency bins may then be subject to decoding to extract the quadrature amplitude modulation (QAM) encoded signals. A more detailed description of xDSL communication, xDSL transceivers and equalizers can be found in U.S. Pat. No. 5,285,474 and U.S. Pat. No. 5,479,447, both to Chow et al., whose contents are incorporated by reference to the extent necessary to understand the present invention.
Before normal operations can begin, however, one must first establish the tap coefficients for the TDF 112a and correction factors for the FEQ 112d. The TDF is normally implemented in executable software code and stored as tap coefficients in a memory associated with the signal processor 112. The same holds for the correction factors of the FEQ. Typically, both of these are established at the time a communication link is set up between an xDSL modem and another communications device via a twisted pair. When a communication link for a static channel is first established, the channel distortion characteristics are determined by transmitting known training signals over the twisted pair, receiving the channel-corrupted signals at the receiver, and employing LMS or some other algorithmic technique to estimate the impulse response of the channel. From these, one may then calculate the taps of the TDF 112a and the correction factors of the FEQ 112d. Ideally, the TDF and FEQ will not only remove ISI, but also account for any attenuation and phase distortion caused by the channel, across all frequencies.
In addition to simply calculating the various tap coefficients and correction factors during training, one must also determine the DMT symbol boundaries. DMT demodulation is predicated on the independence of DMT symbols. The DMT symbols must be independent because the DFT performs circular, rather than linear, convolution. Consequently, receivers must be designed to encapsulate a single and complete DMT symbol for DFT processing. This requires the receivers to be in synchronization with the transmitter's symbol boundary. A more detailed description of synchronization of receivers to transmitters for DMT modulation in xDSL communication can be found in U.S. Pat. No. 5,901,180 to Aslanis et al, and also in T. Pollet et al, "Synchronization With DMT Modulation", IEEE Communications Magazine, April 1999, p. 80-86.
Once created, due to the static nature of the channel's impulse response, the TDF and the FEQ can be used until that particular communication link is terminated. The prior art teaches various techniques to form the time domain filter and a fully-trained frequency domain equalizer. U.S. Pat. No. 5,461,640 and U.S. Pat. No. 5,870,432, whose contents are incorporated by reference to the extent necessary to understand the present invention, exemplify such prior art techniques.
An FEQ for a DMT signal employing, say, N/2=128 discrete frequencies, needs N/2=128 complex coefficients to model the channel and account for the attenuation and phase distortion at each of the discrete frequencies. The length of the TDF 112a, on the other hand, is not based on the number of frequency bins in the DMT symbol. If one were to first create a N-length frequency domain vector comprising the N/2-length FEQ and its conjugates to account for both positive and negative frequencies, and then take its inverse discrete fourier transform (implemented as an IFFT), one would have a TDF which is full-length time-domain "equalizer" filter having N=256 real tap weights. Without loss of generality, it can be shown that TDFs of long length (e.g. those that operate on large number of samples) perform better than those of short length. Thus, a full-length TDF which mitigates the effects of a channel represents the optimal solution to reversing the effects of frequency-dependent amplitude and phase distortion on a received signal, and is achieved when the channel impulse response is reduced to a single impulse upon application of the full-length TDF. Thus, the mitigation is realized through the use of a time-domain linear transversal filter applied to the incoming signal. Generally, the number of modeled poles and zeros present in the channel dictates the required number of taps needed for minimal ripple in the passband of the TDF.
For high-speed digital communications such as xDSL, the useful passband are typically large and thus requires many taps to fully mitigate the effects of the channel. However, the environment of high-speed communications implies that sampled data needs to be processed in a timely fashion. This, in turn, may discourage or prohibit complete mitigation of channel effects if the number of taps in the TDF is large, since the filter must be run every time a sample is introduced in the receiver. In this case, inter-symbol interference (ISI) cannot be eliminated, and as a result symbols must be spaced farther apart in time to account for the "tail" or "bleed-over" of the adjacent symbol.
Additionally, the complexity and computational load of a TDF, which is normally implemented in executable software code resident in a computer readable memory associated with a processor, can become very expensive when one is trying to mitigate ISI in a twisted-pair channel exhibiting a high "eigenvalue spread". And since the TDF must be applied on all incoming samples, the entire process can be time-consuming, ultimately reducing data throughput.
Rather than employ an optimal, or full-length, TDF, one may use a reduced-length TDF having fewer tap coefficients than the full-length TDF. Such a "shortening" TDF, is modeled on a shortened channel impulse response having fewer taps than the original channel impulse response and thus reduces the computational burden. And because of the shortened response, one may transmit symbols closer together, thus increasing the data transmission rate. In fact, current ADSL transmission specifications include a symbol guard-band time implemented via a cyclic prefix. The symbol guard-band spaces the DMT symbols far enough apart for a shortening TDF to reduce the impulse response to less than the cyclic prefix length. This allows for symbol independence, while eliminating the need for a computationally expensive full-length TDF.
One technique for shortening the impulse response is described in J. Chow et al., "A Cost Effective maximum Likelihood Receiver For Multicarrier Systems", Proc. IEE ICC '92 p948-952, Chicago, June 1992. This approach employs the auto-correlation matrix and the cross-correlation matrix of the received signal. The auto-correlation matrix is inverted, multiplied by the cross-correlation matrix, and stored. This result is calculated NM times, N being the length of the time-domain filter to find the best coefficients for shortening the impulse response, and M being a user-defined number of times that the cross-correlation matrix is adjusted to find the best phase offset.
Another technique for shortening the impulse response is described in Falconer & Magee, "Adaptive Channel Memory Truncation for Maximum Likelihood Sequence Estimation", The Bell System Technical Journal, v. 52, No. 9, November 1973. In this technique, the coefficients are formed through a "brute-force" approach. The ratio of energy inside a window of N samples, as compared to the energy outside the window, is maximized subject to certain energy constraints by means of a least-square-error reduction technique. Formation of the energy components involves Cholesky decomposition, matrix inversion, and eigenvalue analysis of Nth-order matrices. Matrix inversion cost is alleviated through the use of the Levinson-Durbin algorithm, which is commonly used to invert Toeplitz matrices, such as the auto-correlation matrices of real-valued samples.
Another technique based on modeling the channel as an auto-regressive (AR) model is described in P. Melsa et al., "Impulse Response Shortening for Discrete Multitone Transceivers", IEEE Trans. On Communications, Vol. 44, No. Dec. 12, 1996. Based on a process length of N taps, the algorithm computes the Nth order AR model using an iterative technique based on a multichannel version of the Levinson algorithm. The computed poles are then used in an all-zero filter to cancel the modeled poles, thus leaving only the finite number of zeros as the CIR.
Finally, aforementioned U.S. Pat. No. 5,285,474 presents an approach to shortening an impulse response in which a target channel is formed through reception of a known training sequence and updated by using an LMS algorithm or complex-valued division. The equalizer uses a truncated target channel along with the received signal and a local copy of the training sequence to update its taps accordingly, also using the LMS algorithm or complex-valued division.